Số tiền thứ tự Tiền_thứ_tự

Số các quan hệ từng loại của tập hợp có n phần tử
Số phần tửBất kìBắc cầuPhản xạĐối xứngTiền thứ tựThứ tự bộ phậnTiền thứ tự toàn phầnThứ tự toàn phầnQuan hệ tương đương
0111111111
1221211111
216134843322
3512171646429191365
465536399440961024355219752415
n2n22n2−n2n(n+1)/2 ∑ k = 0 n k ! S ( n , k ) {\textstyle \sum _{k=0}^{n}k!S(n,k)} n! ∑ k = 0 n S ( n , k ) {\textstyle \sum _{k=0}^{n}S(n,k)}
OEISA002416A006905A053763A006125A000798A001035A000670A000142A000110

Trong đó S(n, k) là số Stirling loại thứ hai.

Có tương ứng một-một giữa các tiền thứ tự và các cặp (phân hoạch của thứ tự riêng phần). Do đó số tiền thứ tự bằng với tổng của số các quan hệ thứ tự riêng phần trên mọi phân hoạch. Ví dụ như sau:

  • Với n = 3 : {\displaystyle n=3:}
    • 1 phân hoạch của 3, có 1 tiền thứ tự
    • 3 phân hoạch của 2 + 1, cho 3 × 3 = 9 {\displaystyle 3\times 3=9} tiền thứ tự
    • 1 phân hoạch của 1 + 1 + 1, cho 19 tiền thứ tự.
    Tính tổng lại ta được 29 tiền thứ tự
  • Với n = 4 : {\displaystyle n=4:}
    • 1 phân hoạch của 4, cho 1 tiền thứ tự
    • 7 phân hoạch của hai lớp (4 của 3 + 1 và 3 của 2 + 2), cho 7 × 3 = 21 {\displaystyle 7\times 3=21} tiền thứ tự
    • 6 phân hoạch của 2 + 1 + 1, cho 6 × 19 = 114 {\displaystyle 6\times 19=114} tiền thứ tự
    • 1 phân hoạch của 1 + 1 + 1 + 1, cho 219 tiền thứ tự
    Tính tổng lại ta được 355 tiền thứ tự